package cn.lbd.arithmetic.leetcode.editor.cn;
//给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。
//
// 给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。 
//
// 
//
// 示例: 
//
// 输入："23"
//输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].
// 
//
// 说明: 
//尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。 
// Related Topics 字符串 回溯算法 
// 👍 934 👎 0


import jdk.internal.org.objectweb.asm.Handle;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

//leetcode submit region begin(Prohibit modification and deletion)
class Solution17 {
    private static Map<Character, String> map = null;

    static {
        map = new HashMap<>();
        map.put('1',null);
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");
    }

    public static List<String> letterCombinations(String digits) {
        List<String> lists = new ArrayList<>();
        if (digits.length() == 0) {
            return lists;
        }
        dfs(lists, 0, new StringBuilder(), digits);
        return lists;
    }

    public static void dfs(List<String> results, int index, StringBuilder temp, String digits) {
        if (temp.length() == digits.length()) {
            results.add(temp.toString());
            return;
        } else {
            char num = digits.charAt(index);
            String letters = map.get(num);
            for (int i = 0; i < letters.length(); i++) {
                temp.append(letters.charAt(i));
                dfs(results, index + 1, temp, digits);
                //回溯后，退到当前节点根节点
                temp.deleteCharAt(index);
            }
        }
    }

    public static void main(String[] args) {
        System.out.println(letterCombinations("249586").toString());
    }
}
//leetcode submit region end(Prohibit modification and deletion)
